#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

class Solution {
private:
    // 调整MAXN大小以适应测试数据范围
    const int MAXN = 301;
    
    // 标记节点是否为初始感染节点（恶意软件源头）
    vector<bool> virus;
    // 记录删除每个源头后能拯救的节点数量
    vector<int> cnts;
    // 标记每个连通分量的感染源头：
    // -1：未被感染源头影响
    // -2：被多个源头影响（无法通过删除单个源头拯救）
    // >=0：被该索引对应的源头感染
    vector<int> infect;
    // 并查集父节点数组
    vector<int> father;
    // 并查集每个集合的大小
    vector<int> size;

public:
    Solution() : virus(MAXN), cnts(MAXN), infect(MAXN), father(MAXN), size(MAXN) {}
    
    // 查找根节点（带路径压缩）
    int find(int i) {
        if (i != father[i]) {
            father[i] = find(father[i]);
        }
        return father[i];
    }
    
    // 合并两个集合
    void unite(int x, int y) {
        int fx = find(x);
        int fy = find(y);
        if (fx != fy) {
            father[fx] = fy;
            size[fy] += size[fx];
        }
    }
    
    // 初始化数据结构
    void build(int n, vector<int>& initial) {
        // 重置所有数组状态
        for (int i = 0; i < n; ++i) {
            virus[i] = false;
            cnts[i] = 0;
            infect[i] = -1;
            size[i] = 1;
            father[i] = i;
        }
        // 标记初始感染节点
        for (int i : initial) {
            virus[i] = true;
        }
    }
    
    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
        int n = graph.size();
        build(n, initial);
        
        // 第一步：合并所有非感染节点（普通节点）
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                // 当两个节点相连且都不是初始感染节点时，合并它们
                if (graph[i][j] == 1 && !virus[i] && !virus[j]) {
                    unite(i, j);
                }
            }
        }
        
        // 第二步：标记每个连通分量的感染源头
        for (int sick : initial) {
            for (int neighbor = 0; neighbor < n; ++neighbor) {
                // 只处理与感染节点直接相连的普通节点
                if (sick != neighbor && !virus[neighbor] && graph[sick][neighbor] == 1) {
                    int fn = find(neighbor);  // 找到该普通节点所在连通分量的根
                    if (infect[fn] == -1) {
                        // 首次发现该连通分量的感染源头
                        infect[fn] = sick;
                    } else if (infect[fn] != -2 && infect[fn] != sick) {
                        // 该连通分量被多个源头感染，标记为无法拯救
                        infect[fn] = -2;
                    }
                }
            }
        }
        
        // 第三步：统计删除每个源头能拯救的节点数量
        for (int i = 0; i < n; ++i) {
            // 只处理连通分量的根节点
            if (i == find(i) && infect[i] >= 0) {
                // 累加该连通分量的大小到对应源头的拯救计数中
                cnts[infect[i]] += size[i];
            }
        }
        
        // 第四步：找到最优解（拯救节点最多的源头，若有多个则选索引最小的）
        sort(initial.begin(), initial.end());  // 先排序保证索引小的优先
        int ans = initial[0];
        int maxSave = cnts[ans];
        for (int i : initial) {
            if (cnts[i] > maxSave) {
                ans = i;
                maxSave = cnts[i];
            }
        }
        
        return ans;
    }
};

